package com.guaoran.algorithm.two.pointer;

import java.util.Arrays;

/**
 * @Auth gucheng
 * @Desc 双指针 求有序数组的两个元素相加之和为 target 的元素下标
 * @Date 2021/1/8 下午4:37
 */
public class TwoSum {
    public static void main(String[] args) {
        System.out.println(Arrays.toString(twoSum(new int[]{2, 7, 11, 15}, 9)));
        System.out.println(twoSumNum(new int[]{2,3,4,5,6,7,10},9));
        System.out.println(Arrays.toString(twoSum2(new int[]{3,3},6)));
    }

    /**
     * 求有序数组的两个元素相加之和为 target 的元素下标
     * @param nums 【[2,7,11,15], target = 9】 、【 [2,3,4], target = 6】、【 [-1,0], target = -1】
     * @param target
     * @return
     */
    public static int[] twoSum(int[] nums,int target){
        int[] result = {-1,-1};
        if(nums == null || nums.length == 0){
            return result;
        }
        int start = 0;
        int end = nums.length -1;
        while(start < end){
            if(nums[start] + nums[end] < target){
                start ++;
            } else if (nums[start] + nums[end] > target){
                end --;
            } else{
                result[0] = start + 1;
                result[1] = end + 1;
                return result;
            }
        }
        return result;
    }

    /**
     * 获取满足和的数量
     * @param nums
     * @param target
     * @return
     */
    public static int twoSumNum(int[] nums,int target){
        if(nums == null || nums.length == 0){
            return 0;
        }
        int num = 0;
        int start = 0;
        int end = nums.length -1;
        while (start<end){
            if (nums[start] + nums[end] < target){
                start ++;
            } else if (nums[start] + nums[end] > target){
                end --;
            } else {
               start ++;
               end --;
               num ++;
            }
        }
        return num;
    }

    /**
     * 两数相加
     * Input : nums = [2,7,11,15], target = 9 => Output : [0,1]
     * Input : nums = [3,2,4], target = 6 => Output : [1,2]
     * Input : nums = [3,3], target = 6 => Output : [0,1]
     * https://leetcode.com/problems/two-sum/
     * @param nums
     * @param target
     * @return
     */
    public static int[] twoSum2(int[]nums,int target){
        int[] result = {-1,-1};
        if(nums == null || nums.length < 2){
            return result;
        }
        int[] newNums = Arrays.copyOf(nums,nums.length);
        Arrays.sort(newNums);
        int start = 0;
        int end = newNums.length -1;
        int a=-1,b=-1;
        // 获取 相加为 target 的值
        while(start < end){
            if(newNums[start] + newNums[end]==target){
                a=newNums[start];
                b=newNums[end];
                break;
            }else if(newNums[start]+newNums[end] >target){
                end --;
            }else{
                start ++;
            }
        }
        if(a==-1 && b==-1){
            return result;
        }

        // 分别获取 a 和 b 的下标
        for(int i = 0;i<nums.length;i++){
            if(result[0] ==-1) {
                if (a == nums[i]) {
                    result[0] = i;
                    continue;
                }
            }
            if(result[1]==-1) {
                if (b == nums[i]) {
                    result[1] = i;
                    continue;
                }
            }
        }
        return result;
    }

}
